Search for: All records

Consider the following stochastic matching problem. We are given a known graph 𝐺 = (𝑉 , 𝐸). An unknown subgraph 𝐺𝑝 = (𝑉 , 𝐸𝑝 ) is realized where 𝐸𝑝 includes every edge of 𝐸 independently with some probability 𝑝 ∈ (0, 1]. The goal is to query a sparse subgraph 𝐻 of 𝐺, such that the realized edges in 𝐻 include an approximate maximum matching of 𝐺𝑝 . This problem has been studied extensively over the last decade due to its applications in kidney exchange, online dating, and online labor markets. For any fixed 𝜀 > 0, [BDH STOC’20] showed that any graph 𝐺 has a subgraph 𝐻 with quasipoly(1/𝑝) = (1/𝑝)poly(log(1/𝑝 ) ) maximum degree, achieving a (1 − 𝜀)-approximation. A major open question is the best approximation achievable with poly(1/𝑝)- degree subgraphs. A long line of work has progressively improved the approximation in the poly(1/𝑝)-degree regime from .5 [BDH+ EC’15] to .501 [AKL EC’17], .656 [BHFR SODA’19], .666 [AB SOSA’19], .731 [BBD SODA’22] (bipartite graphs), and most recently to .68 [DS ’24]. In this work, we show that a poly(1/𝑝)-degree subgraph can obtain a (1 − 𝜀)-approximation for any desirably small fixed 𝜀 > 0, achieving the best of both worlds. Beyond its quantitative improvement, a key conceptual contribu- tion of our work is to connect local computation algorithms (LCAs) to the stochastic matching problem for the first time. While prior work on LCAs mainly focuses on their out-queries (the number of vertices probed to produce the output of a given vertex), our analysis also bounds the in-queries (the number of vertices that probe a given vertex). We prove that the outputs of LCAs with bounded in- and out-queries (in-n-out LCAs for short) have limited correlation, a property that our analysis crucially relies on and might find applications beyond stochastic matchings.